一看到求什么“最大的最小值”，“最小的最大值”就马上想到二分（还有可能是单调队列）
再仔细看看题目，貌似没什么头绪，但答案似乎存在单调性，果断二分。
答案肯定在0到n范围内。
设$f[i]$为做到第$i$个作业时所需要花的最短时间。
假如我们可以空$k$道题（二分出来的）
$f[i]=min(f[i],f[j]+a[i])$
其中 $$i-k+1 \le j < i$$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36//90分，超时
using namespace std;
const int MAXN=50004;
int n,t;
int a[MAXN],f[MAXN];
bool check(int k){
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=k;i++)f[i]=a[i];
for(int i=k+1;i<=n;i++){
for(int j=i-k-1;j<i;j++){
f[i]=min(f[i],f[j]+a[i]);
}
}
int ans=1<<30;
for(int i=n-k;i<=n;i++)ans=min(f[i],ans);
if(ans<=t)return 1;
return 0;
}
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int l=0,r=n,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
return 0;
}
如果你想要满分，就要减少枚举量，就是减少枚举j的次数。
我们要维护一个区间最小数，可以用线段树来写，我这里采用的是优先队列。
采用优先队列有一个原则，那就是队列里的元素要单调，并且还要有另一个条件限制它们，我比较喜欢叫做“保质期”（因为保质期是不变的但是时间在变）
这个题目单调队列里的元素的保质期就是下标，如果他的下表不满足上面的枚举j的条件，这个元素就“过期”了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
const int MAXN=50004;
int n,t;
int a[MAXN],f[MAXN];
deque<pair<int,int> >q;
bool check(int k){
memset(f,0x3f,sizeof(f));
while(q.size())q.pop_front();
f[0]=0;
//q.push_back(make_pair(0,0));加上这句话就不用分开处理
for(int i=1;i<=k+1;i++){
f[i]=a[i];
while(q.size()&&q.back().first>=a[i])q.pop_back();
q.push_back(make_pair(a[i],i));
}
for(int i=k+2;i<=n;i++){
// cout<<q.front().first<<" "<<q.front().second<<" "<<i-k-1<<endl;
while(q.size()&&q.front().second<i-k-1)q.pop_front();
f[i]=min(f[i],q.front().first+a[i]);
while(q.size()&&q.back().first>=f[i])q.pop_back();
q.push_back(make_pair(f[i],i));
}
int ans=1<<30;
for(int i=n-k;i<=n;i++)ans=min(f[i],ans);
if(ans<=t)return 1;
return 0;
}
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int l=0,r=n,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid))r=mid-1,ans=mid;
else l=mid+1;
}
cout<<ans;
return 0;
}